package bit;

import java.util.HashSet;
import java.util.Set;

/**
 *
 * 参考  https://leetcode-cn.com/problems/single-number-iii/solution/dong-hua-tu-jie-yi-ding-neng-hui-by-yuan-gqg8/
 * 只有一个数字时  全部异或即可  因为两个相同的数异或为0 0异或任何数等于他本身  最后结果肯定是那个数
 * 有两个只出现一次的数  其他都是重复出现的  可以分成两组 保证这两个数字分到两个组中 最后每个组内异或就行
 *
 * 分组原理   所有数字异或   相同的异或成了0   这两个不同的异或完了  肯定有一个二进制位是不同的  用这一位来分类即可
 * 其他位运算题目
 * 136. 只出现一次的数字
 * 137. 只出现一次的数字 II
 * 645. 错误的集合
 * 260. 只出现一次的数字 III
 */
class 只出现一次的数字_136 { public int singleNumber(int[] nums) { for(int i= 1; i< nums.length; i++) { nums[0] ^= nums[i]; } return nums[0]; } }
class 只出现一次的数字II_137 {
    public int singleNumber(int[] nums) {
        // 通用方法 每位取余
        int[] mark = new int[32];
        for (int num : nums) {
            for (int i = 0; i < 32; i++) {
                // & 1 == 1 表示该位为1  ; ^1 == 0 表示按位异或   前面的位不同 也会等于0  因此不能用 ^1 == 0
                if (((num >> i) & 1) == 1) {
                    mark[i]++;
                }
            }
        }
        int res = 0;

        for (int i = 0; i < 32; i++) {
            if (((mark[i] % 3) & 1) == 1) {
                res += 1 << i;
            }
        }
        return res;
    }
}
class 只出现一次的数字III_260{
            public int[] singleNumber(int[] nums) {
                // 求 只出现一次的两个值的异或  按其最右边的1 位分两组   
                // 因为相同的数字肯定在一组内  
                // 异或位为1  恰出现一次的两个值该位肯定不同

                int t = nums[0];
                for(int i = 1; i< nums.length; i++) {
                     t ^= nums[i];
                }
                //  也可以 int div = 1;
                //  while ((div & ret) == 0) {
                //    div <<= 1;
                // }
                // 求最左边的1
                int group = t & (-t);
                // 0 异或任何数字等于其本身
                int a = 0; int b = 0;
                for(int i = 0; i< nums.length; i++) {
                    if((group & nums[i]) == 0) {
                        a ^= nums[i];
                    } else {
                        b ^= nums[i];
                    }
                }
                return new int[]{a, b};
            }

        }


         


